package com.tql.TreeTest;

import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        TreeNode treeNodeE = new TreeNode(1);
        TreeNode treeNodeF= new TreeNode(2);
        TreeNode treeNodeA= new TreeNode(9,treeNodeE,treeNodeF);
        List<Integer> integers = inorderTraversal(treeNodeA);
        System.out.println(integers);

    }
    /*
    * 94. 二叉树的中序遍历
    * */
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }
    //中序遍历 先遍历左子树，根节点、右子树
    public static void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
    //前序遍历 先遍历根节点、然后左子树，右子树
    public static void inorder1(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
    //后序遍历 先遍历左子树，右子树，最后根节点
    public static void inorder2(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        inorder(root.left, res);
        inorder(root.right, res);
        res.add(root.val);
    }
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    /*
    * 101. 对称二叉树
    * */
    public boolean isSymmetric(TreeNode root) {
       return check(root,root);
    }

    public boolean check(TreeNode p, TreeNode q) {
        if(p==null&&q==null){
            return true;
        }
        if(p==null ||q==null){
            return false;
        }
        return q.val==p.val&&check(q.left,p.right)&&check(q.right,p.left);
    }
    /*
    * 110. 平衡二叉树
    * */
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return Math.max(height(root.left), height(root.right)) + 1;
        }
   }
   /*
   * 226. 翻转二叉树
   * */
    public TreeNode invertTree(TreeNode root) {
        if(root==null) return null;
        invertTree(root.left);
        invertTree(root.right);
        TreeNode temp=root.left;
        root.left=root.right;
        root.left=temp;
        return root;
    }
}


